#include <iostream>
#include <vector>
using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int n = dungeon.size(), m = dungeon[0].size();
    vector<vector<int>> dp(n, vector<int>(m));
    if (dungeon[n - 1][m - 1] <= 0)
        dp[n - 1][m - 1] = -dungeon[n - 1][m - 1] + 1;
    else
        dp[n - 1][m - 1] = 1;
    for (int j = m - 2; j >= 0; j--) {
        if (dungeon[n - 1][j] <= 0)
            dp[n - 1][j] = -dungeon[n - 1][j] + dp[n - 1][j + 1];
        else if (dungeon[n - 1][j] >= dp[n - 1][j + 1])
            dp[n - 1][j] = 1;
        else
            dp[n - 1][j] = dp[n - 1][j + 1] - dungeon[n - 1][j];
    }

    for (int i = n - 2; i >= 0; i--) {
        if (dungeon[i][m - 1] <= 0)
            dp[i][m - 1] = -dungeon[i][m - 1] + dp[i + 1][m - 1];
        else if (dungeon[i][m - 1] >= dp[i + 1][m - 1])
            dp[i][m - 1] = 1;
        else
            dp[i][m - 1] = dp[i + 1][m - 1] - dungeon[i][m - 1];
    }

    for (int i = n - 2; i >= 0; i--) {
        for (int j = m - 2; j >= 0; j--) {
            if (dp[i + 1][j] < dp[i][j + 1]) {
                if (dungeon[i][j] < 0)
                    dp[i][j] = -dungeon[i][j] + dp[i + 1][j];
                else if (dungeon[i][j] >= dp[i + 1][j])
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i + 1][j] - dungeon[i][j];
            } else {
                if (dungeon[i][j] < 0)
                    dp[i][j] = -dungeon[i][j] + dp[i][j + 1];
                else if (dungeon[i][j] > dp[i][j + 1])
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i][j + 1] - dungeon[i][j];
            }
        }
    }
    return dp[0][0];
}